package turkey;

import java.util.Arrays;
import java.util.List;

import static java.lang.Math.abs;

/**
 * 基于 Dijkstra 算法求最短路径 Java实现
 */
public class Dijkstra {

    public static int[][] calculateShortestPath(int[][] map, int[] start, int[] target){
        //计算权重矩阵
        int[][] WeightMatrix = creatWeightMatrix(map);
        //给出 起点和终点计算出最短路径
        int startLocation = start[0] * map[0].length + start[1];
        int targetLocation = target[0] * map[0].length + target[1];
        List<String> path = dijkstra(WeightMatrix, startLocation, targetLocation);
        return null;
    }

    public static int calculateNextLocation(int[][] map, int start, int target){
        //计算权重矩阵
        int[][] WeightMatrix = creatWeightMatrix(map);
        List<String> path = dijkstra(WeightMatrix, start, target);
        int nextLocation = Integer.parseInt(path.get(1));
//        int i = nextLocation / map[0].length;
//        int j = nextLocation % map[0].length;
//        return new int[]{i,j};
        return nextLocation;
    }


    public static List<String> dijkstra(int[][] weight, int start, int end) {
        int n = weight.length;
        int[] shortPath = new int[n];
        String[] newPath = new String[n];
        for (int i = 0; i < n; i++) {
            newPath[i] = new String(start + "," + i);
        }
        int[] visited = new int[n];
        shortPath[start] = 0;
        visited[start] = 1;
        for (int count = 1; count < n; count++) {
            int k = -1;
            int dmin = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][i] < dmin) {
                    dmin = weight[start][i];
                    k = i;
                }
            }
            shortPath[k] = dmin;
            visited[k] = 1;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
                    weight[start][i] = weight[start][k] + weight[k][i];
                    newPath[i] = newPath[k] + "," + i;
                }
            }
        }
        String shPath = newPath[end];
        String str[] = shPath.split(",");
        List<String> list = Arrays.asList(str) ;
//        System.out.println("step:--"+list);
        return list;
    }

    /**
     * 根据 二维数组生成权重矩阵
     * @param data
     * @return
     */
    public static int[][] creatWeightMatrix(int[][] data){

        int row = data.length;
        int column = data[0].length;
        int matrixDimension = row * column;
        int[][] weightMatrix = new int[matrixDimension][matrixDimension];
        for(int i = 0; i < matrixDimension; i++){
            //生成初始位置
            int H = i / column;
            int L = i % column;
            for(int j = 0; j < matrixDimension; j++){
                // 生成实际运算位置
                int wH = j / column ;
                int wL = j % column ;
                // 基于行判断
                Boolean hp = (H == wH) && (abs(wL - L) <= 1);
                // 基于列判断
                Boolean lp = (L == wL) && (abs(wH - H) <= 1);
                int temp;
                if( hp || lp){
                    temp = abs(wH - H)  + abs(wL - L) + data[wH][wL];
                }else {
                    temp = 999;
                }
                weightMatrix[i][j] = temp;
            }
        }
//        System.out.println(Arrays.toString(weightMatrix));
//        for (int i = 0; i < data.length; i++) {
//            for (int j = 0; j < data[0].length; j++) {
//                System.out.print(data[i][j]+" ");
//
//            }
//            System.out.println();
//        }
        return weightMatrix;
    }
}
